In an increasingly mobile world, a huge amount of information derived from mobile devices is available for application developers to take advantage of. However, access to raw data is rarely sufficient and may prove too cumbersome. Particularly at location-based services (LBS), processing of raw location data may be complex and extensive so that it should not be performed by mobile devices with restricted resources. Usually application developers rely on frameworks that provide some kind of pre-processing on the data, enabling higher-level abstractions and richer applications.
Geofencing is one such higher-level abstraction. The Geofencing problem consists in, given two consecutive location updates previous location (PL) and current location (CL), determining a set of areas (or geofences) of interest exited between the two locations, as well as a set of areas of interest entered, with the intention of generating an action regarding these entered and exited areas.
FIG. 1 illustrates the basic concept of the Geofencing problem. At a first location update, a mobile device is located at a previous location PL within Area1. At a second location update performed after the first location update, the mobile device is located at a current location CL within Area2. This means that the mobile device has moved from PL to CL and from Area1 to Area2. A Geofencing system would trigger Area1 as being exited and Area2 as being entered.
A straightforward algorithm for calculating exited and entered geofences is to first get the set of geofences inside which the previous location PL is contained in (set Previous) and the set of geofences inside which the current location CL is contained in (set Current). The sets Exited and Entered (referring to exited and entered geofences) can be determined as follows:Entered=Current−Previous:={x∈Current|x∉Previous}Exited=Previous−Current:={x∈Previous|x∉Current}
This means that set Entered contains each geofences of the set Current which is not contained in the set Previous.
With the explosion of Location-Based Services which make use of geo-tagged data, as well as the ever-increasing number of mobile devices which enable these services, strategies need to be employed to handle the large amounts of data involved. Additionally, responses to a large number of queries have to be generated. Current state-of-the-art in geo-tagged data indexing employ some kind of partitioning mechanism to better distribute data and balance load.
One approach is disclosed by Jinbao Wang et al. “Indexing multidimensional data in a cloud system” (SIGMOD 10, 2010) which uses a RT-CAN (R-Tree based index in CAN) based approach. The global index is disseminated to different cluster servers which are organized as a logical CAN (Content Addressable Network) based overlay network. Several algorithms (one of them dynamic) are used to optimize the system, thus reducing query and index maintenance costs.
In a Geofencing system, when different areas are partitioned across different servers the algorithm requires that all servers calculate the sets Current and Previous, and then operate on both these sets to calculate entered and exited areas respectively (as detailed in the previous two formulas). This means either the two sets are forwarded by the different servers to a third server, responsible for subtracting the sets, or the sets are themselves exchanged between the two servers which then do the subtraction. This results in high latency and a large number of messages to be exchanged between the servers.
LBSs is a very hot topic at the present, naturally exploiting the nature of an increasingly “connected” world, where all kinds of mobile devices are present. U.S. Pat. No. 7,848,765 B2 discloses a variety of methods and systems relating to LBSs. However, its content does not provide any help regarding reduction of latency or of the number of exchanged messages.